package a2022.a20221031;

/**
 * @author lenovo
 * @date 2022/10/31
 */
public class a {
    public static void main(String[] args) {
        System.out.println(magicalString(9));
    }

    //1 2 2 1 1 2 1 2 2 1 2 2 1 1 2 1 1 2 2 1 2 1 1
    public static int magicalString2(int n) {
        StringBuilder s = new StringBuilder("122");
        int i = 2, a = 1;
        if (n < 4) return 1;
        while (i < n - 1) {
            s.append(s.charAt(i) == '2' ?
                    a == 1 ? "11" : "22" :
                    a == 1 ? "1" : "2");
            a ^= 3;
            i++;
        }
        String sub = s.substring(0, n);
        return sub.length() - sub.replaceAll("1", "").length();
    }

    public static int magicalString(int n) {
        char[] s = new char[n + 2];
        s[0] = 1;
        s[1] = s[2] = 2;
        char c = 2;
        for (int i = 2, j = 3; j < n; ++i) {
            c ^= 3; // 1^3=2, 2^3=1，这样就能在 1 和 2 之间转换
            s[j++] = c;
            if (s[i] == 2) s[j++] = c;
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) ans += 2 - s[i]; // 2-1=1，2-2=0，这样就只统计了 1
        return ans;
    }

}
